from typing import List


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        lp = len(prices)
        # dp = [[-prices[0], 0, 0]]
        dp0, dp1, dp2 = -prices[0], 0, 0
        ans = 0
        for i in range(1, lp):
            # dp0 = max(dp[i-1][0], dp[i-1][2]-prices[i])
            # dp1 = dp[i-1][0] + prices[i]
            # dp2 = max(dp[i-1][1], dp[i-1][2])
            # dp.append([dp0, dp1, dp2])
            # dp.append([
            #     max(dp[i-1][0], dp[i-1][2]-prices[i]),
            #     dp[i-1][0] + prices[i],
            #     max(dp[i-1][1], dp[i-1][2]),
            # ])
            dp10 = max(dp0, dp2-prices[i])
            dp11 = dp0 + prices[i]
            dp12 = max(dp1, dp2)
            dp0, dp1, dp2 = dp10, dp11, dp12
        # ans = max(dp[lp-1])
        ans = max(dp0, dp1, dp2)
        return ans


solve = Solution()

questions = [
    ([1, 2, 3, 0, 2],),
]

for qi, q in enumerate(questions):
    print(f'#{qi}:', q)
    print('ans:', solve.maxProfit(q[0]))

